#include <iostream>
#include <vector>

using namespace std;
// 622. 设计循环队列
// 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则
// 并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

class MyCircularQueue {
private:
    vector<int> q;  // 数组模拟循环队列，存放队列中元素
    int front, rear;    // 队头，队尾指针
    int capacity;   // 队列容量
public:
    // 构造器，设置队列长度为 k 。
    MyCircularQueue(int k) {
        capacity = k + 1;   // 要多分配一个空间
        q = vector<int>(capacity);
        front = rear = 0;   // 队空初始化
    }
    // 向循环队列插入一个元素。如果成功插入则返回真。
    bool enQueue(int value) {
        if(isFull()) return false;
        q[rear] = value;
        rear = (rear+1) % capacity; // 后移一位
        return true;
    }
    // 从循环队列中删除一个元素。如果成功删除则返回真。
    bool deQueue() {
        if(isEmpty()) return false;
        front = (front + 1) % capacity; // 后移一位。这里没有返回出队的元素
        return true;
    }
    // 从队首获取元素。如果队列为空，返回 -1 。
    int Front() {
        if(isEmpty()) return -1;
        return q[front];
    }
    // 获取队尾元素。如果队列为空，返回 -1 。
    int Rear() {
        if(isEmpty()) return -1;
        return q[(rear - 1 + capacity) % capacity];
    }
    // 检查循环队列是否为空。
    bool isEmpty() {
        return rear == front;
    }
    // 检查循环队列是否已满。
    bool isFull() {
        return (rear+1) % capacity == front;
    }

};

int main() {
    MyCircularQueue circularQueue = MyCircularQueue(3); // 设置长度为 3
    cout << boolalpha << circularQueue.enQueue(1) << endl;  // 返回 true
    cout << boolalpha << circularQueue.enQueue(2) << endl;  // 返回 true
    cout << boolalpha << circularQueue.enQueue(3) << endl;  // 返回 true
    cout << boolalpha << circularQueue.enQueue(4) << endl;  // 返回 false，队列已满
    cout << circularQueue.Rear() << endl;  // 返回 3
    cout << boolalpha << circularQueue.isFull() << endl;  // 返回 true
    cout << boolalpha << circularQueue.deQueue() << endl;  // 返回 true
    cout << boolalpha << circularQueue.enQueue(4) << endl;  // 返回 true
    cout << boolalpha << circularQueue.Rear() << endl;  // 返回 4
    return 0;
}
